import java.util.ArrayList;
import java.util.List;
//https://leetcode.cn/problems/letter-case-permutation/
class Solution {
    List<String> ret;
    StringBuffer path;

    public List<String> letterCasePermutation(String ss) {
        ret = new ArrayList<>();
        path = new StringBuffer();
        char[] s = ss.toCharArray();
        dfs(s, 0);
        return ret;
    }

    public void dfs(char[] s, int pos) {
        if(pos == s.length) {
            ret.add(path.toString());
            return;
        }
        char ch = s[pos];
        //不变(不管是数字字符还是字母都有不变的分支)
        path.append(ch);
        dfs(s, pos + 1);
        //回溯
        path.deleteCharAt(path.length() - 1);

        //变
        if(ch < '0' || ch > '9') {
            char tmp = change(ch);
            path.append(tmp);
            dfs(s, pos + 1);
            //回溯
            path.deleteCharAt(path.length() - 1);
        }
    }
    public char change(char ch) {
        if(ch >= 'a' && ch <= 'z') return ch -= 32;
        else return ch += 32;
    }
}